package com.yvon.service.demo.algorithm.offer;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 栈的压入、弹出序列
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9831.%20%E6%A0%88%E7%9A%84%E5%8E%8B%E5%85%A5%E3%80%81%E5%BC%B9%E5%87%BA%E5%BA%8F%E5%88%97/README
 */
public class P31 {
    public static void main(String[] args) {
        Solution solution = new P31().new Solution();
        boolean b = solution.validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1});
        System.out.println(b);
    }

    /**
     * 建立一个辅助栈s,把序列1,2,3,4,5依次压入辅助栈s，并按照第二个序列4,5,3,2,1的顺序从辅助栈s中弹出数字。
     * 先将序列1,2,3,4,5依次压入栈s，每次压栈时都判断栈s的当前栈顶元素跟序列4,5,3,2,1的第一个元素是否相等。
     * 当压入4之后，发现栈顶元素跟序列4,5,3,2,1的第一个元素相等。
     * 弹出栈s的栈顶元素4，然后将序列4,5,3,2,1中第一个元素去掉，序列4,5,3,2,1变成序列5,3,2,1。在执行上述过程。
     * 直到s为空，返回true；
     * https://blog.csdn.net/zcw4237256/article/details/79539816
     */
    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> s = new ArrayDeque<>();
            int q = 0;
            for (int num : pushed) {
                s.push(num);
                while (!s.isEmpty() && s.peek() == popped[q]) {
                    s.pop();
                    ++q;
                }
            }
            return s.isEmpty();
        }
    }
}
